package NO3_LinkedList;

import java.util.ArrayList;

/**
 * 2025-08-29
 * 力扣 - 86. 分隔链表
 * <p>
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
 * 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 */
public class PartitionMain {
    public static void main(String[] args) {
        ListNode head = new ListNode(
                1,
                new ListNode(4,
                        new ListNode(3,
                                new ListNode(2,
                                        new ListNode(5,
                                                new ListNode(2))))));
        ListNode.printList(partition(head, 3));
    }

    public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ArrayList<ListNode> smallList = new ArrayList<>();
        ArrayList<ListNode> largeList = new ArrayList<>();

        // 遍历链表
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                smallList.add(new ListNode(current.val));
            } else {
                largeList.add(new ListNode(current.val));
            }
            current = current.next;
        }

        // 构建新链表
        for (int i = 0; i < smallList.size() - 1; i++) {
            smallList.get(i).next = smallList.get(i + 1);
        }
        for (int i = 0; i < largeList.size() - 1; i++) {
            largeList.get(i).next = largeList.get(i + 1);
        }

        // 处理连接和尾节点
        if (!smallList.isEmpty()) {
            if (!largeList.isEmpty()){
                smallList.get(smallList.size() - 1).next = largeList.get(0);
                largeList.get(largeList.size() - 1).next = null;
            } else {
                smallList.get(smallList.size() - 1).next = null;
            }
        }

        return smallList.isEmpty() ? largeList.get(0) : smallList.get(0);
    }
}
